2019牛客暑期多校训练营(第八场)Flower Dance(有坑)

发表于 | 分类于 ， | 阅读次数：
本文字数： 4k | 阅读时长 ≈ 4 分钟

2019牛客暑期多校训练营(第八场)Flower Dance
题意: 给$n$个点 $m$条边，每条边有一个权值区间，表示能通过这个区间的 值的范围，问从$1$到$n$可以通过的权值有多少个。
题解:

1.DFS线段树+离散化+并查集

这个线段树，其实也不能算是个正常的线段树，他build 的之后就没啥用了，没有更新和查询.。。直接在线段树上dfs,首先把权值离散化，然后存入线段树中，线段树每个节点表示，区间[l,r]，中有哪些边，这样每次深搜下去，经过的边用并查集维护起来，表示哪些点是联通的，然后如果，1和n联通的话就更新权值。这题有回溯，就有拆边，所以并查集要保存路径，而且要加按秩合并的优化,不然会超时。
写离散化线段树尽量保存 (l,r] 左开右闭的区间值，保存[l,r] 的区间会出问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid ((l + r) >> 1)
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid, r, chr
#define eb(x) emplace_back(x)
#define pb(x) emplace_back(x)
#define mem(a, b) memset(a, b, sizeof(a));

const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;

#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

//typedef __int128 LLL;

template<typename T>
void read(T &w) {//读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))
        w = w * 10 + (c & 15);
}

template<typename T>
void output(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    int ss[55], sp = 0;
    do
        ss[++sp] = x % 10;
    while (x /= 10);
    while (sp)
        putchar(48 + ss[sp--]);
}

struct edge {
    int u, v, l, r;
} eg[maxn];


vector<int> v;

int get(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int n, m;
vector<int> dat[maxn];

void build(int l, int r, int k, int a, int b, int x) {
    if (l == a && b == r) {
        dat[k].emplace_back(x);
        return;
    }
    if (b <= mid) {
        build(lson, a, b, x);
    } else if (a >= mid) {
        build(rson, a, b, x);
    } else {
        build(lson, a, mid, x);
        build(rson, mid, b, x);
    }
}

vector<int> d[maxn];
int ans = 0;
int par[maxn];

int find(int x) {
    return (par[x] == x) ? x : find(par[x]);
}

int rk[maxn];

void unit(int x, int y, int dep) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (rk[x] < rk[y])swap(x, y);
        par[y] = x;
        d[dep].emplace_back(y);
        if (rk[x] == rk[y])rk[x]++;
    }
}

void dfs(int l, int r, int k, int dep) {
    d[dep].clear();
    for (auto au:dat[k]) {
        unit(eg[au].u, eg[au].v, dep);
    }
    if (find(1) == find(n)) {
        ans += v[r - 1] - v[l - 1];
    } else if (r != l + 1) {
        dfs(lson, dep + 1);
        dfs(rson, dep + 1);
    }
    for (auto au:d[dep]) {
        par[au] = au;
    }
}

int main() {
    f();
    read(n);
    read(m);
    for (int i = 0; i <= n; i++)par[i] = i;
    for (int i = 0; i < m; i++) {
        read(eg[i].u);
        read(eg[i].v);
        read(eg[i].l);
        read(eg[i].r);
        v.emplace_back(eg[i].l);
        v.emplace_back(eg[i].r + 1);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int mx = v.size();
    for (int i = 0; i < m; i++) {
        build(1, mx, 1, get(eg[i].l), get(eg[i].r + 1), i);
    }
    dfs(1, mx, 1, 0);
    output(ans);
    puts("");

#ifndef ONLINE_JUDGE
    cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

LCT+最小生成树 挖个坑，懒得学splay